package com.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 树遍历
 *
 * @author winson
 * @create 2022-03-31 23:29
 */
public class TraversalSolution {

    /**
     * 中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        /**
         * 递归遍历树
         * 左中右
         */
        List<Integer> list = new ArrayList<>();
        inorder(list, root);
        return list;
    }

    public void inorder(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        /**
         * 左中右节点
         */
        inorder(list, root.left);
        list.add(root.val);
        inorder(list, root.right);
    }

    public List<Integer> middleTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        /**
         * 迭代遍历
         */
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode treeNode = stack.pop();
            list.add(treeNode.val);
            root = treeNode.right;
        }
        return list;
    }

    /**
     * 前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorder(list, root);
        return list;
    }

    public void preorder(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preorder(list, root.left);
        preorder(list, root.right);
    }

    public List<Integer> preOrderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode treeNode = stack.pop();
            root = treeNode.right;
        }
        return list;
    }
}
